package com.cuz.for2024;

import java.util.HashMap;
import java.util.Map;

public class T76 {
    public static void main(String[] args) {
        System.out.println(new T76().minWindow("a", "a"));
    }
    public String minWindow(String s, String t) {
        char[] tArray = t.toCharArray();
        Map<Character, Integer> tMap = new HashMap<>();
        for (char c : tArray) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        Map<Character, Integer> countMap = new HashMap<>();

        char[] sArray = s.toCharArray();
        int left = 0;
        int right = 0;

        int minLen = Integer.MAX_VALUE;
        int start = -1;
        int end = -1;
        while (right < sArray.length) {
            char nowChar = sArray[right];
            if (tMap.containsKey(nowChar)) {
                countMap.put(nowChar, countMap.getOrDefault(nowChar, 0) + 1);
            }

            while (match(tMap, countMap) && left <= right) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                    end = left + minLen;
                }
                if (tMap.containsKey(sArray[left])) {
                    countMap.put(sArray[left], countMap.get(sArray[left]) - 1);
                }
                left++;
            }
            right++;
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, end);
    }

    private boolean match(Map<Character, Integer> tMap,
                          Map<Character, Integer> countMap) {
        for (Map.Entry<Character, Integer> tE : tMap.entrySet()) {
            Character tChar = tE.getKey();
            Integer tCount = tE.getValue();
            Integer countMapC = countMap.getOrDefault(tChar, -1);
            if (tCount > countMapC) {
                return false;
            }
        }
        return true;
    }
}
